﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace KATS_Client.FileNameData
{
    /// <summary>
    /// Get the Levenshtein Edit Distance.
    /// </summary>
    /// <see cref="http://blogs.msdn.com/toub/archive/2006/05/05/590814.aspx"/>
    public static class LevenshteinDistance
    {
        /// <SUMMARY>Computes the Levenshtein Edit Distance between two enumerables.</SUMMARY>
        /// <TYPEPARAM name="T">The type of the items in the enumerables.</TYPEPARAM>
        /// <PARAM name="x">The first enumerable.</PARAM>
        /// <PARAM name="y">The second enumerable.</PARAM>
        /// <RETURNS>The edit distance.</RETURNS>
        private static int EditDistance<T>(IEnumerable<T> x, IEnumerable<T> y)
            where T : IEquatable<T>
        {
            // Validate parameters
            if (x == null) throw new ArgumentNullException("x");
            if (y == null) throw new ArgumentNullException("y");

            // Convert the parameters into IList instances
            // in order to obtain indexing capabilities
            IList<T> first = x as IList<T> ?? new List<T>(x);
            IList<T> second = y as IList<T> ?? new List<T>(y);

            // Get the length of both.  If either is 0, return
            // the length of the other, since that number of insertions
            // would be required.
            int n = first.Count, m = second.Count;
            if (n == 0) return m;
            if (m == 0) return n;

            // Rather than maintain an entire matrix (which would require O(n*m) space),
            // just store the current row and the next row, each of which has a length m+1,
            // so just O(m) space. Initialize the current row.
            int curRow = 0, nextRow = 1;
            int[][] rows = new int[][] { new int[m + 1], new int[m + 1] };
            for (int j = 0; j <= m; ++j) rows[curRow][j] = j;

            // For each virtual row (since we only have physical storage for two)
            for (int i = 1; i <= n; ++i)
            {
                // Fill in the values in the row
                rows[nextRow][0] = i;
                for (int j = 1; j <= m; ++j)
                {
                    int dist1 = rows[curRow][j] + 1;
                    int dist2 = rows[nextRow][j - 1] + 1;
                    int dist3 = rows[curRow][j - 1] +
                        (first[i - 1].Equals(second[j - 1]) ? 0 : 1);

                    rows[nextRow][j] = Math.Min(dist1, Math.Min(dist2, dist3));
                }

                // Swap the current and next rows
                if (curRow == 0)
                {
                    curRow = 1;
                    nextRow = 0;
                }
                else
                {
                    curRow = 0;
                    nextRow = 1;
                }
            }

            // Return the computed edit distance
            return rows[curRow][m];
        }

        /// <summary>
        /// Get a similarity rating. 0 = not similar. 100 = identical
        /// </summary>
        /// <param name="x">Parameter 1</param>
        /// <param name="y">Parameter 2</param>
        /// <returns>int 0-100. where 0 = not similar. 100 = identical</returns>
        public static int GetSimilarity<T>(IEnumerable<T> x, IEnumerable<T> y)
            where T : IEquatable<T>
        {
            // Validate parameters
            if (x == null) throw new ArgumentNullException("x");
            if (y == null) throw new ArgumentNullException("y");

            // Convert the parameters into IList instances
            // in order to obtain indexing capabilities
            IList<T> first = x as IList<T> ?? new List<T>(x);
            IList<T> second = y as IList<T> ?? new List<T>(y);
            int max =Math.Max(first.Count,second.Count);


            int result = EditDistance(x, y);

            if (result == 0)
            {
                // then they are identical
                return 100;
            }
            
            if (result == max)
            {
                // then they are completely different
                return 0;
            }

            /*
             * so since 
             *  result = 0           means identical
             *  result = max(x1,x2)  means completely different
             * then
             *  (1-result/max)*100 
             * will map to
             *  100 mean identical
             *  0   mean completely different
             *  
             * This can be expresssed most efficiently as
             * (max-result)*100/max
             */

            return (max - result) * 100 / max;
        }
    }
}
